/* 数组相关操作:
无序数组需要排序的最短子数组长度
数组的子数组最大累加和
数组的子数组最大累乘积
二分查找
斐波那契查找
冒泡排序
快速排序
选择排序
插入排序
希尔排序
归并排序
堆排序
 */
 
//无序数组需要排序的最短子数组长度
public int getMinLength(int[] arr){
	if(arr==null||arr.length<2){
		return 0;
	}
	int min = arr[arr.length-1];
	int noMinIndex = -1;
	for(int i=arr.length-2;i>=0;i--){
		if(arr[i]>min){
			noMinIndex=i;
		}else{
			min = arr[i];
		}
	}
	if(noMinIndex==-1){
		return 0;
	}
	int max = arr[0];
	int noMaxIndex = -1;
	for(int i=1;i<arr.length;i++){
		if(arr[i]<max){
			noMaxIndex = i;
		}else{
			max=arr[i];
		}
	}
	return noMaxIndex-noMinIndex+1;
}

//数组的子数组最大累加和
public int maxSum(int[] arr){
	if(arr==null||arr.length==0){
		return 0;
	}
	int max=Integer.MIN_VALUE;
	int cur=0;
	for(int i=0;i<arr.length;i++){
		cur +=arr[i];
		max =Math.max(max,cur);
		cur=cur<0?0:cur;
	}
	return max;
}

//数组的子数组最大累乘积
public double maxProduct(double[] arr){
	if(arr==null||arr.length==0){
		return 0;
	}
	double max = arr[0];
	double min = arr[0];
	double res = arr[0];
	double maxEnd=0;
	double minEnd=0;
	for(int i=1;i<arr.length;i++){
		maxEnd = max*arr[i];
		minEnd = min*arr[i];
		max = Math.max(Math.max(maxEnd,minEnd),arr[i]);
		min = Math.min(Math.min(maxEnd,minEnd),arr[i]);
		res = Math.max(res,max);
	}
	return res;
}

//二分查找
public int BinarySearch(int[] arr,int low,int high,int K){
	if(K<arr[low]||K>arr[high]||low>high){
		return -1;
	}
	int middle = (low+high)/2;
	//int middle = low+(K-arr[low])/(arr[high]-arr[low])*(high-low); 这是插值查找
	if(arr[middle]==K){
		return middle;
	}else if(arr[middle]>K){
		return BinarySearch(arr,low,middle-1,K);
	}else{
		return BinarySearch(arr,middle+1,high,K);
	}
}
public int BinarySearch2(int[] arr,int K){
	int low =0;
	int high=arr.length-1;
	if(K<arr[low]||K>arr[high]||low>high){
		return -1;
	}
	while(low<=high){
		int middle = (low+high)/2;
		if(arr[middle]==K){
			return middle;
		}else if(arr[middle]<K){
			low=middle+1;
		}else{
			high=middle-1;
		}
		
	}
	return -1;
}

//斐波那契查找
public int[] fibonacci(){
	int[] f = new int[20];
	int i=0;
	f[0] = 1;
	f[1] = 1;
	for(i=2;i<MAXSIZE;i++){
		f[i] = f[i-1]+f[i-2];
	}
	return f;
}
public int fibonacciSearch(int[] arr, int key){
	int low = 0;
	int high = arr.length-1;
	int k=0;
	int[] f = fibonacci();
	while(arr.length>f[k]-1){
		k++;
	}
	int[] temp = new int[f[k]-1];
	for(int j=0;l<arr.length;j++){
		temp[j] = arr[j];
	}
	for(int i=arr.length;i<f[k]-1;i++){
		temp[i] = temp[high];
	}
	while(low<=high){
		int mid = low + f[k-1] - 1;
		if(temp[mid]>key){
			high = mid - 1;
			k-=1;
		}else if(temp[mid]<key){
			low = mid + 1;
			k-=2;
		}else{
			if(mid<arr.length){
				return mid;
			}else{
				return arr.length-1;
			}
		}
	}
	return -1;
}

//冒泡排序
public void bubbleSort(int[] arr){
	if(arr==null||arr.length<2){
		return;
	}
	for(i=0;i<arr.length-1;i++){
		for(j=0;j<arr.length-1-i;j++){
			if(arr[j]>arr[j+1]){
				int temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1]= temp;
			}
		}
	}
}

//快速排序
public int getMiddle(int[] arr,int low,int high){
	int temp = number[low];
	while(low<high){
		while(low<high&&arr[high]>=temp){
			high--;
		}
		arr[low]=arr[high];
		while(low<high&&arr[low]<=temp){
			low++;
		}
		arr[high]=arr[low];
	}
	arr[low] = temp;
	return low;	
}
public void quickSort(int[] arr,int low,int high){
	if(low<high){
		int middle = getMiddle(arr,low,high);
		quickSort(arr,low,middle-1);
		quickSort(arr,middle+1,high);
	}
}

//选择排序
public void selectSort(int[] arr){
	for(i=0;i<arr.length;i++){
		int k=i;
		for(int j=i+1;j<arr.length;j++){
			if(a[k]>a[j]){
				k=j;
			}
		}
		int temp = arr[i];
		arr[i] = arr[k];
		arr[k] = temp;
	}
}

//插入排序
public void insertSort(int[] arr){
	for(int i=0;i<arr.length;i++){
		int temp = arr[i];
		int j;
		for(j=i;j>0&&temp<arr[j-1];j--){
			arr[j-1]=arr[j];
		}
		arr[j]=temp;
	}
}

//希尔排序
public void shellSort(int[] arr){
	int j;
	int temp=0;
	for(int increment = arr.length/2;increment>0;increment/=2){
		for(int i=increment;i<arr.length;i++){
			temp = arr[i];
			for(j=i;j>=increment;j-=increment){
				if(temp<arr[j-increment]){
					arr[j]=arr[j-increment];
				}else{
					break;
				}
			}
			arr[j]=temp;
		}
	}
}

//归并排序
public void mergeSort(int[] arr,int low,int high){
	int middle = (low+high)/2;
	if(low<high){
		mergeSort(arr,low,middle);
		mergeSort(arr,middle+1,high);
		merge(arr,low,middle,high);
	}else{
		return;
	}
}
public void merge(int[] arr,int low,int mid,int high){
	int[] temp = new int[high-low+1];
	int i = low;
	int j = mid+1;
	int k =0;
	while(i<=mid&&j<=high){
		if(arr[i]<arr[j]){
			temp[k++] = arr[i++];
		}else{
			temp[k++] = arr[j++];
		}
	}
	while(i<=mid){
		temp[k++] = arr[i++];
	}
	while(j<=high){
		temp[k++] = arr[j++];
	}
	for(int m=0;m<temp.length;m++){
		arr[m+low] = temp[m];
	}
}

//堆排序
public void heapSort(int[] arr){
	for(i=0;i<arr.length-1;i++){
		buildMaxHeap(arr,arr.length-1-i);
		swap(a,0,arr.length-1-i);
	}
}	
public void buildMaxHeap(int[] arr;int lastIndex){
	for(int i=(lastIndex-1)/2;i>=0;i--){
		int parent = i;
		while(2*parent+1<=lastIndex){
			int biggerIndex = 2*parent+1;
			if(biggerIndex<lastIndex){
				if(arr[biggerIndex]<arr[biggerIndex+1]){
					biggerIndex++;
				}
			}
			if(arr[parent]<arr[biggerIndex]){
				swap(arr,parent,biggerIndex);
				parent = biggerIndex;
			}else{
				break;
			}
		}
	}
}	
public void swap(int[] arr,int i,int j){
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 